Reinforcement learning (RL) provides a principled framework for decision-making in partially observable environments, which can be modeled as Markov decision processes and compactly represented through dynamic decision Bayesian networks. Recent advances demonstrate that inference on sparse Bayesian networks can be accelerated using quantum rejection sampling combined with amplitude amplification, leading to a computational speedup in estimating acceptance probabilities.\\ Building on this result, we introduce Quantum Bayesian Reinforcement Learning (QBRL), a hybrid quantum-classical look-ahead algorithm for model-based RL in partially observable environments. We present a rigorous, oracle-free time complexity analysis under fault-tolerant assumptions for the quantum device. Unlike standard treatments that assume a black-box oracle, we explicitly specify the inference process, allowing our bounds to more accurately reflect the true computational cost. We show that, for environments whose dynamics form a sparse Bayesian network, horizon-based near-optimal planning can be achieved sub-quadratically faster through quantum-enhanced belief updates. Furthermore, we present numerical experiments benchmarking QBRL against its classical counterpart on simple yet illustrative decision-making tasks. Our results offer a detailed analysis of how the quantum computational advantage translates into decision-making performance, highlighting that the magnitude of the advantage can vary significantly across different deployment settings.

I want to build a model for Chess/Go/Shogi that is trained and tested on real players, and I want it to pass the Turing test. I don't want my model to play the best move in a position, I want it to play the move that a person would play (of a certain strength, time control, etc..). It's easy to make this a classification problem and train a CNN on a one-hot encoded policy of actual moves played. The only problem is, without some kind of look-ahead algorithm (MCTS for example) the model fails to learn sequences that require multiple moves, such as tactics. However, current MCTS/alpha-beta/minimax models require evaluation of leaf nodes. I don't have a way to shape the reward to an evaluation of a leaf node.